//合并区间
/*以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。*/
struct comp {
    bool operator()(vector<int>& x, vector<int>& y) { return x[0] < y[0]; }
};
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> arr;
        sort(intervals.begin(), intervals.end(), comp());
        arr.push_back(intervals[0]);
        for (int i = 1; i < intervals.size(); i++) {
            if (arr[arr.size() - 1][1] < intervals[i][0])
                arr.push_back(intervals[i]);
            else if (arr[arr.size() - 1][1] < intervals[i][1]) {
                arr[arr.size() - 1][1] = intervals[i][1];
            }
        }
        return arr;
    }
};
//串联所有单词的子串
/*给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。

 s 中的 串联子串 是指一个包含  words 中所有字符串以任意顺序排列连接起来的子串。

例如，如果 words = ["ab","cd","ef"]， 那么 "abcdef"， "abefcd"，"cdabef"， "cdefab"，"efabcd"， 和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串，因为他不是任何 words 排列的连接。
返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。
1 <= s.length <= 104
1 <= words.length <= 5000
1 <= words[i].length <= 30
words[i] 和 s 由小写英文字母组成
*/
class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        unordered_map<string, int> hash2;
       
        vector<int> arr;
        for (auto& _s : words) {
            hash2[_s]++;
        }
        for (int i = 0; i < words[0].size(); i++) {
            unordered_map<string, int> hash1;
            int left = i, right = i;
            int count = 0;
            right += words[0].size();
            while (right <= s.size()) {
                string temp(s.begin() + right - words[0].size(),
                            s.begin() + right);
                hash1[temp]++;
                if (hash1[temp] <= hash2[temp])
                    count++;
                if (right - left > words[0].size() * words.size()) {
                    string _temp(s.begin() + left,
                                 s.begin() + left + words[0].size());
                    if (hash1[_temp] <= hash2[_temp])
                        count--;
                    hash1[_temp]--;
                    left += words[0].size();
                }
                if (count == words.size())
                    arr.push_back(left);
                right += words[0].size();
            }
        }
        return arr;
    }
};
//最小覆盖子串
/*给定两个字符串 s 和 t 。返回 s 中包含 t 的所有字符的最短子字符串。如果 s 中不存在符合条件的子字符串，则返回空字符串 "" 。

如果 s 中存在多个符合条件的子字符串，返回任意一个。

 

注意： 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。*/

class Solution {
public:
    string minWindow(string s, string t) {
        int hash1[128] = {0};
        int hash2[128] = {0};
        for (auto& c : t) {
            hash2[c]++;
        }
        int count = 0;
        int left = 0, right = 0;
        int ret = s.size() + 1;
        int min_index = -1;
        while (right < s.size()) {
            hash1[s[right]]++;
            if (hash1[s[right]] <= hash2[s[right]])
                count++;
            while (count == t.size()) {
                if (ret > right - left + 1) {
                    ret = right - left + 1;
                    min_index = left;
                }
                if (hash1[s[left]] <= hash2[s[left]])
                    count--;
                hash1[s[left]]--;
                left++;
            }
            right++;
        }
        if (min_index == -1)
            return {""};
        else
            return s.substr(min_index, ret);
    }
};